package search

// https://leetcode-cn.com/problems/search-insert-position/
// 寻找插入的位置
// 算法: 二分查找
// 时间复杂度: O(logn)
func SearchInsert(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}
	return binaryInsert(nums, 0, len(nums)-1, target)
}

func binaryInsert(nums []int, start, end, target int) int {
	if start == end {
		if target <= nums[start] {
			return start
		} else {
			return start + 1
		}
	}

	if start == end-1 {
		if target <= nums[start] {
			return start
		} else if target <= nums[end] {
			return end
		} else {
			return end + 1
		}
	}

	mid := (start + end) / 2
	if target <= nums[mid] {
		return binaryInsert(nums, start, mid-1, target)
	} else {
		return binaryInsert(nums, mid+1, end, target)
	}
}
